#pragma once
#include<iostream>

namespace ForcibleBugMaker
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>(const K& k = K(), const V& v = V())
			:_key(k)
			, _value(v)
			, _left(nullptr)
			, _right(nullptr)
		{}
		K _key;
		V _value;
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
	};

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree() = default;

		BSTree(const BSTree<K, V>& t)
		{
			_root = _Copy(t._root);
		}

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr) {
				_root = new Node(key, value);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur){
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else return false;
			}
			if (parent->_key < key) parent->_right = new Node(key, value);
			else parent->_left = new Node(key, value);
			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key)
					cur = cur->_right;
				else if (cur->_key > key)
					cur = cur->_left;
				else return cur;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					if (cur == _root && cur->_left == nullptr) {
						_root = cur->_right;
						delete cur;
						return true;
					}
					else if (cur == _root && cur->_right == nullptr) {
						_root = cur->_left;
						delete cur;
						return true;
					}
					if (cur->_left == nullptr) {
						if (parent->_right == cur)
							parent->_right = cur->_right;
						else
							parent->_left = cur->_right;
						delete cur;
					}
					else if (cur->_right == nullptr) {
						if (parent->_right == cur)
							parent->_right = cur->_left;
						else
							parent->_left = cur->_left;
						delete cur;
					}
					else {
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left) {
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_key = rightMin->_key;
						cur->_value = rightMin->_value;
						if (rightMinP == cur)
							rightMinP->_right = rightMin->_right;
						else
							rightMinP->_left = rightMin->_right;
						delete rightMin;
					}
					return true;
				}
			}
			return false;
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}
		void InOrder()
		{
			_InOrder(_root);
			std::cout << std::endl;
		}
	private:
		Node* _Copy(Node* root)
		{
			if (root == nullptr)return nullptr;
			Node* newRoot = new Node(root->_key, root->_value);
			newRoot->_left = _Copy(root->_left);
			newRoot->_right = _Copy(root->_right);
			return newRoot;
		}

		void Destroy(Node* root)
		{
			if (root == nullptr)return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)return;
			_InOrder(root->_left);
			std::cout << root->_key << ":" << root->_value << " ";
			_InOrder(root->_right);
		}
		Node* _root = nullptr;
	};
}